package nachos.threads;

import nachos.machine.*;

/////////////// BEGIN HENRI ///////////////////
import java.util.Comparator;
import java.util.PriorityQueue;
/////////////// END HENRI ///////////////////

/**
 * Uses the hardware timer to provide preemption, and to allow threads to sleep
 * until a certain time.
 */
public class Alarm {
    /**
     * Allocate a new Alarm. Set the machine's timer interrupt handler to this
     * alarm's callback.
     *
     * <p><b>Note</b>: Nachos will not function correctly with more than one
     * alarm.
     */
    public Alarm() {
	Machine.timer().setInterruptHandler(new Runnable() {
		public void run() { timerInterrupt(); }
	    });
	//////////////////// BEGIN HENRI ////////////////////

	/* Create the priority list of sleeping threads */	
   	Comparator<SleepingThread> comparator = new SleepingThreadComparator();
       	sleepingThreadQueue = new PriorityQueue<SleepingThread>(10,comparator);

	//////////////////// END HENRI ////////////////////
    }

    /**
     * The timer interrupt handler. This is called by the machine's timer
     * periodically (approximately every 500 clock ticks). Causes the current
     * thread to yield, forcing a context switch if there is another thread
     * that should be run.
     */
    public void timerInterrupt() {
	Lib.debug(dbgAlarm,"In Interrupt Handler (time = "+Machine.timer().getTime()+")");
	KThread.currentThread().yield();

        /////////////////////// BEGIN HENRI ////////////////////

	/* Disable interrupts */
        boolean intStatus = Machine.interrupt().disable();

	SleepingThread st = sleepingThreadQueue.peek();
	while ((st != null) && (st.date <= Machine.timer().getTime())) {
	  sleepingThreadQueue.remove(st); 
	  Lib.debug(dbgAlarm,"Unblocking thread " + st.thread.toString() +
                             "("+st.date+" <= "+Machine.timer().getTime());
	  st.thread.ready();
          st = sleepingThreadQueue.peek();
        }
	
	/* Restore interrupts */
        Machine.interrupt().restore(intStatus);

        /////////////////////// END HENRI ////////////////////
    }

    /**
     * Put the current thread to sleep for at least <i>x</i> ticks,
     * waking it up in the timer interrupt handler. The thread must be
     * woken up (placed in the scheduler ready set) during the first timer
     * interrupt where
     *
     * <p><blockquote>
     * (current time) >= (WaitUntil called time)+(x)
     * </blockquote>
     *
     * @param	x	the minimum number of clock ticks to wait.
     *
     * @see	nachos.machine.Timer#getTime()
     */
    public void waitUntil(long x) {
	// for now, cheat just to get something working (busy waiting is bad)
	// long wakeTime = Machine.timer().getTime() + x;
	// while (wakeTime > Machine.timer().getTime())
	//    KThread.yield();

        ////////////////// BEGIN HENRI ////////////////////

 	/* If x <= 0, then no waiting */
	if (x <= 0)
          return;

	/* Disable interrupts */
        boolean intStatus = Machine.interrupt().disable();

	/* Create a SleepingThread object and put it in the priority queue */
 	SleepingThread st = new SleepingThread(KThread.currentThread(), 
                                               Machine.timer().getTime() + x);	
	sleepingThreadQueue.offer(st);

	Lib.debug(dbgAlarm,"Blocking thread " + KThread.currentThread().toString() +
                           "until date " + st.date);

	/* Put the thread in the blocked state */
	KThread.currentThread().sleep();

	/* Restore interrupts */
        Machine.interrupt().restore(intStatus);

        ////////////////// END HENRI ////////////////////

    }

    /**
     * Tests whether this module is working.
     */
    public static void selfTest() {
	AlarmTest.runTest();
    }

    private static final char dbgAlarm = 'a';

    ////////////////// BEGIN HENRI ////////////////////

    /* A data structure to keep track of threads still
     * waiting to be awakened when their times come */
    private PriorityQueue<SleepingThread> sleepingThreadQueue;


    /* A class to store a thread and a number of ticks */
    private class SleepingThread {
      public SleepingThread(KThread thread, long date) {
        this.thread = thread;
        this.date = date;
      }
     
      public KThread thread;
      public long date; 
    }

    private class SleepingThreadComparator implements Comparator<SleepingThread> {
      public int compare(SleepingThread st1, SleepingThread st2) {
        if (st1.date < st2.date) {
          return -1;
        } else if (st1.date > st2.date) {
          return 1;
        } else {
          return 0;
        }
      } 
    }
    ////////////////// END HENRI ////////////////////
}
